#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<unordered_map>
#include<algorithm>
using namespace std;
class Solution1
{
public:
    int lenLongestFibSubseq(vector<int>& arr)
    {
        int n = arr.size();
        int ret = 0;
        vector<vector<int>> dp(n, vector<int>(n, 2));
        unordered_map<int, int> hash;
        for (int i = 0;i < n;i++) hash[arr[i]] = i;
        for (int i = 2;i < n;i++)
            for (int j = 1;j < i;j++)
            {
                if (i == 6 && j == 1)
                {
                    int a = 0;
                }
                if (hash.count(arr[i] - arr[j]) && hash[arr[i] - arr[j]]<j)
                {
                    int index = hash[arr[i] - arr[j]];
                    dp[i][j] = max(dp[i][j], dp[j][index] + 1);
                    ret = max(ret, dp[i][j]);
                    if (ret == 6)
                    {
                        int a = 0;
                    }
                }
            }
        return ret;

    }
};
class Solution
{
public:
    int numberOfArithmeticSlices(vector<int>& nums)
    {
        int ret = 0;
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        unordered_map<long long, vector<int>> hash;
        for (int i = 0;i < n;i++) hash[nums[i]].push_back(i);
        for (int i = 2;i < n;i++)
            for (int j = 1;j < i;j++)
            {
                int a = 2 * nums[j] - nums[i];
                if (hash.count(a))
                {
                    for (auto& x : hash[a])
                        if (x < j)
                            dp[i][j] += (dp[j][x] + 1);
                    ret += dp[i][j];
                }
            }
        return ret;
    }
};
int main()
{
    vector<int> v = { 2,4,6,8,10 };
    Solution().numberOfArithmeticSlices(v);
	return 0;
}